

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">

<html>


<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">

<base target="_top">
<style type="text/css">
  

/* default css */

table {
  font-size: 1em;
  line-height: inherit;
  border-collapse: collapse;
}


tr {
  
  text-align: left;
  
}


div, address, ol, ul, li, option, select {
  margin-top: 0px;
  margin-bottom: 0px;
}

p {
  margin: 0px;
}


pre {
  font-family: Courier New;
  white-space: pre-wrap;
  margin:0;
}

body {
  margin: 6px;
  padding: 0px;
  font-family: Verdana, sans-serif;
  font-size: 10pt;
  background-color: #ffffff;
  color: #000;
}


img {
  -moz-force-broken-image-icon: 1;
}

@media screen {
  html.pageview {
    background-color: #f3f3f3 !important;
    overflow-x: hidden;
    overflow-y: scroll;
  }

  

  body {
    min-height: 1100px;
    
    counter-reset: __goog_page__;
  }
  
  * html body {
    height: 1100px;
  }
  /* Prevent repaint errors when scrolling in Safari. This "Star-7" css hack
     targets Safari 3.1, but not WebKit nightlies and presumably Safari 4.
     That's OK because this bug is fixed in WebKit nightlies/Safari 4 :-). */
  html*#wys_frame::before {
    content: '\A0';
    position: fixed;
    overflow: hidden;
    width: 0;
    height: 0;
    top: 0;
    left: 0;
  }
  
  .pageview body {
    border-top: 1px solid #ccc;
    border-left: 1px solid #ccc;
    border-right: 2px solid #bbb;
    border-bottom: 2px solid #bbb;
    width: 648px !important;
    margin: 15px auto 25px;
    padding: 40px 50px;
  }
  /* IE6 */
  * html {
    overflow-y: scroll;
  }
  * html.pageview body {
    overflow-x: auto;
  }
  

  
    
    .writely-callout-data {
      display: none;
    }
    

    .writely-footnote-marker {
      background-image: url('MISSING');
      background-color: transparent;
      background-repeat: no-repeat;
      width: 7px;
      overflow: hidden;
      height: 16px;
      vertical-align: top;

      
      -moz-user-select: none;
    }
    .editor .writely-footnote-marker {
      cursor: move;
    }
    .writely-footnote-marker-highlight {
      background-position: -15px 0;
      -moz-user-select: text;
    }
    .writely-footnote-hide-selection ::-moz-selection, .writely-footnote-hide-selection::-moz-selection {
      background: transparent;
    }
    .writely-footnote-hide-selection ::selection, .writely-footnote-hide-selection::selection {
      background: transparent;
    }
    .writely-footnote-hide-selection {
      cursor: move;
    }

    /* Comments */
    .writely-comment-yellow {
      background-color: #ffffd7;
    }
    .writely-comment-orange {
      background-color: #ffe3c0;
    }
    .writely-comment-pink {
      background-color: #ffd7ff;
    }
    .writely-comment-green {
      background-color: #d7ffd7;
    }
    .writely-comment-blue {
      background-color: #d7ffff;
    }
    .writely-comment-purple {
      background-color: #eed7ff;
    }

  


  
  .br_fix span+br:not(:-moz-last-node) {
    
    position:relative;
    
    left: -1ex
    
  }

  
  #cb-p-tgt {
    font-size: 8pt;
    padding: .4em;
    background-color: #ddd;
    color: #333;
  }
  #cb-p-tgt-can {
    text-decoration: underline;
    color: #36c;
    font-weight: bold;
    margin-left: 2em;
  }
  #cb-p-tgt .spin {
    width: 16px;
    height: 16px;
    background: url(//ssl.gstatic.com/docs/clipboard/spin_16o.gif) no-repeat;
  }
}

h6 { font-size: 8pt }
h5 { font-size: 8pt }
h4 { font-size: 10pt }
h3 { font-size: 12pt }
h2 { font-size: 14pt }
h1 { font-size: 18pt }

blockquote {padding: 10px; border: 1px #DDD dashed }

.webkit-indent-blockquote { border: none; }

a img {border: 0}

.pb {
  border-width: 0;
  page-break-after: always;
  /* We don't want this to be resizeable, so enforce a width and height
     using !important */
  height: 1px !important;
  width: 100% !important;
}

.editor .pb {
  border-top: 1px dashed #C0C0C0;
  border-bottom: 1px dashed #C0C0C0;
}

div.google_header, div.google_footer {
  position: relative;
  margin-top: 1em;
  margin-bottom: 1em;
}


/* Table of contents */
.editor div.writely-toc {
  background-color: #f3f3f3;
  border: 1px solid #ccc;
}
.writely-toc > ol {
  padding-left: 3em;
  font-weight: bold;
}
ol.writely-toc-subheading {
  padding-left: 1em;
  font-weight: normal;
}
/* IE6 only */
* html writely-toc ol {
  list-style-position: inside;
}
.writely-toc-none {
  list-style-type: none;
}
.writely-toc-decimal {
  list-style-type: decimal;
}
.writely-toc-upper-alpha {
  list-style-type: upper-alpha;
}
.writely-toc-lower-alpha {
  list-style-type: lower-alpha;
}
.writely-toc-upper-roman {
  list-style-type: upper-roman;
}
.writely-toc-lower-roman {
  list-style-type: lower-roman;
}
.writely-toc-disc {
  list-style-type: disc;
}

/* Ordered lists converted to numbered lists can preserve ordered types, and
   vice versa. This is confusing, so disallow it */
ul[type="i"], ul[type="I"], ul[type="1"], ul[type="a"], ul[type="A"] {
  list-style-type: disc;
}

ol[type="disc"], ol[type="circle"], ol[type="square"] {
  list-style-type: decimal;
}

/* end default css */


  /* default print css */
  @media print {
    body {
      padding: 0;
      margin: 0;
    }

    div.google_header, div.google_footer {
      display: block;
      min-height: 0;
      border: none;
    }

    div.google_header {
      flow: static(header);
    }

    /* used to insert page numbers */
    div.google_header::before, div.google_footer::before {
      position: absolute;
      top: 0;
    }

    div.google_footer {
      flow: static(footer);
    }

    /* always consider this element at the start of the doc */
    div#google_footer {
      flow: static(footer, start);
    }

    span.google_pagenumber {
      content: counter(page);
    }

    span.google_pagecount {
      content: counter(pages);
    }

    .endnotes {
      page: endnote;
    }

    /* MLA specifies that endnotes title should be 1" margin from the top of the page. */
    @page endnote {
      margin-top: 1in;
    }

    callout.google_footnote {
      
      display: prince-footnote;
      footnote-style-position: inside;
      /* These styles keep the footnote from taking on the style of the text
         surrounding the footnote marker. They can be overridden in the
         document CSS. */
      color: #000;
      font-family: Verdana;
      font-size: 10.0pt;
      font-weight: normal;
    }

    /* Table of contents */
    #WritelyTableOfContents a::after {
      content: leader('.') target-counter(attr(href), page);
    }

    #WritelyTableOfContents a {
      text-decoration: none;
      color: black;
    }

    /* Comments */
    .writely-comment-yellow {
      background-color: #ffffd7;
    }
    .writely-comment-orange {
      background-color: #ffe3c0;
    }
    .writely-comment-pink {
      background-color: #ffd7ff;
    }
    .writely-comment-green {
      background-color: #d7ffd7;
    }
    .writely-comment-blue {
      background-color: #d7ffff;
    }
    .writely-comment-purple {
      background-color: #eed7ff;
    }
  }

  @page {
    @top {
      content: flow(header);
    }
    @bottom {
      content: flow(footer);
    }
    @footnotes {
      border-top: solid black thin;
      padding-top: 8pt;
    }
  }
  /* end default print css */


/* custom css */


/* end custom css */

/* ui edited css */

body {
  font-family: Verdana;
  
  font-size: 10.0pt;
  line-height: normal;
  background-color: #ffffff;
}
/* end ui edited css */


/* editor CSS */
.editor a:visited {color: #551A8B}
.editor table.zeroBorder {border: 1px dotted gray}
.editor table.zeroBorder td {border: 1px dotted gray}
.editor table.zeroBorder th {border: 1px dotted gray}


.editor div.google_header, .editor div.google_footer {
  border: 2px #DDDDDD dashed;
  position: static;
  width: 100%;
  min-height: 2em;
}

.editor .misspell {background-color: yellow}

.editor .writely-comment {
  font-size: 9pt;
  line-height: 1.4;
  padding: 1px;
  border: 1px dashed #C0C0C0
}


/* end editor CSS */

</style>

  
  <title>W4 Procesy </title>

</head>

<body 
    
    >
    
    
    
<div id=vc7a style=TEXT-ALIGN:left>
  <b style=COLOR:#3d85c6><font size=5>Procesy</font></b><br>
  <hr size=2><br>
  Wykład ten ma na celu przedstawienie przekroju zagadnień związanych z procesami w kontekście projektowania systemów rozproszonych. Zarządzanie procesami jest nieodzowną częścią każdego systemu operacyjnego. Procesy są pewnego rodzaju zasobami, którymi trzeba odpowiednio dysponować. Zadanie jest tym trudniejsze im bardziej rozbudowany jest system. Liczba problemów pojawiających się przy zarządzaniu procesami w środowiskach rozproszonych znacząco rośnie w stosunku do tych w systemach scentralizowanych. Poznanie chociaż części zagadnień, wchodzących w skład ogólnie rozumianych procesów pozwoli m.in. na lepsze zrozumienie modelów przetwarzania w systemach rozproszonych.
  <p>
    Po wprowadzeniu pojęć procesów i wątków przejdziemy do omówienia ich wykorzystania w wielowątkowych architekturach klient-serwer. Zaprezentowana zostanie również koncepcja serwera obiektowego oraz adaptera obiektów. W dalszej części skupimy się na problematyce wędrówki procesów w systemach rozproszonych.
  </p>
  <p>
    Następnie przedstawiony zostanie model agentów programowych, który to będzie pewnym rozszerzeniem pojęcia procesów.
  </p>
  <p>
    Wykład będzie również obejmował wybrane zagadnienia związane z zarządzaniem zasobami (ang. <i>resource</i> <i>management</i> ), które są mocno powiązane m.in. z szeregowaniem procesów.
  </p>
  <br>
  <br>
  <b style=COLOR:#3d85c6><font size=3>Procesy rozproszone</font></b><br>
  <hr size=2><br>
</div>
<div id=t9vo style=TEXT-ALIGN:left>
  <img src="images/dcjpvv6n_2325cmxvdzhc_b.png" style=HEIGHT:341px;WIDTH:500px><br>
  <br>
  Gdy bliżej przyjrzeć się rozproszonym systemom operacyjnym natrafimy na pojęcie procesu rozproszonego.<br>
  <br>
  <p>
    <b>Proces</b> <b>rozproszony</b> (ang. <i>distributed</i> <i>process</i> ) jest uogólnieniem pojęcia procesu sekwencyjnego, a dokładniej jest on definiowany jako pewien zbiór procesów sekwencyjnych, czyli takich które reprezentują wykonanie pewnego ciągu operacji. Dodatkowo zakłada się, że procesy wchodzące w skład procesu rozproszonego mogą być <b>współbieżne</b> (ang. <i>concurrent</i> ), a ich działanie jest skoordynowane, tak aby mogły zrealizować pewien wspólny cel.<br>
  </p>
  <p>
    <br>
  </p>
  <p>
    Podobnie do procesów wykonywanych w systemie scentralizowanym, procesy wykonywane w systemie rozproszonym mogą znajdować się w pewnych stanach np.: gotowy, aktywny, oczekujący, zawieszony. Jednakże w przeciwieństwie do procesów w systemach nierozproszonych, procesy rozproszone mogą znajdować się w różnych stanach na różnych maszynach.<br>
  </p>
  <p>
    <br>
  </p>
  <p>
    Wyróżnia się dwa modele rozproszonych procesów: <b>model</b> <b>statyczny</b> (ang. <i>static</i> <i>process</i> <i>model</i> <b>),</b> <b>model</b> <b>dynamiczny</b> (ang. <i>dynamic</i> <i>process</i> <i>model</i> ).<br>
  </p>
  <p>
    <br>
  </p>
  <p>
    W modelu statycznym zakłada się, że procesy, które tworzą pewne zadanie, tworzone są na początku jego działania. Drugi model nie nakłada takiego ograniczenia i procesy można tworzyć i niszczyć w dowolnym momencie trwania programu – zadania.
  </p>
  <br>
  <br>
  <b style=COLOR:#3d85c6><font size=3>Procesy</font></b><br>
  <hr size=2><br>
  <div id=jopp style=TEXT-ALIGN:left>
    <img src="images/dcjpvv6n_2326gbct93gf_b.png" style=HEIGHT:341px;WIDTH:500px>
  </div>
  <br>
  Pojęcie <b>procesu</b> (ang. <i>process</i> ) jest jednym z ważniejszych zagadnień omawianych w ramach systemów operacyjnych i dotyczy to również rozproszonych systemów operacyjnych. Najczęściej proces jest opisywany jako program w trakcie wykonywania. Należy podkreślić, iż nie jest on jedynie kodem programu, który ma za zadanie wykonać pewną sekwencję operacji. Z procesem związane są również pewne stany, w których może się on znajdować.<br>
  <br>
  <p>
    <b>Zarządzanie</b> <b>procesami</b> (ang. <i>process</i> <i>management</i> ) odnosi się do wielu innych tematów związanych z systemami operacyjnymi m.in.: komunikacji międzyprocesowej (ang<i>.</i> <i>Inter-Process</i> <i>Communication</i> - IPC), szeregowania procesów (ang. <i>process</i> <i>scheduling</i> ), synchronizowania procesów (ang<i>.</i> <i>synchronization</i> ), nazewnictwa (ang<i>.</i> <i>naming</i> ). Oczywiście są jeszcze inne istotne kwestie, jak np. zarządzanie pamięcią, które wraz z zarządcą procesu pozwala zapewnić odpowiednie <b>środowisko</b> <b>wykonywania</b> dla procesów (ang. <i>execution</i> <i>environment</i> ). Ponieważ szczegóły dotyczące koncepcji procesu zostały przedstawione na wykładach o systemach operacyjnych, tutaj skupimy się na własnościach procesów szczególnie istotnych w kontekście systemów rozproszonych.<br>
  </p>
  <p>
    <br>
  </p>
  <p>
    W tradycyjnym jednoprocesorowym systemie system operacyjny zarządza pewną pulą procesów do wykonania. Ponieważ procesów jest wiele, a jednostka centralna tylko jedna, następuje współdzielenie procesora. To z kolei wiąże się z dosyć kosztownym <b>przełączaniem</b> <b>kontekstu</b> <b>procesów</b> (ang. <i>context</i> <i>switching</i> ), wobec których system operacyjny stara się zachować transparentność tej operacji. Inaczej rzecz ujmując, to system operacyjny dba o to aby procesy nie musiały zajmować się szczegółami zarządzania sobą. Samo przełączanie procesów implikuje „przełączanie” wielu powiązanych z nim zasobów: kontekstu procesora, rejestrów jednostki zarządzania pamięcią (MMU), podręcznej pamięci tłumaczenia adresów itp. Innymi słowy zapamiętany zostaje stan procesu, a na jego miejsce wstawiany jest stan innego procesu gotowego do wykonania. Ponieważ wielozadaniowość i współbieżność są nieodzownymi cechami systemów rozproszonych, takie przełączanie procesów stało się ważnym problemem. Aby częściowo rozwiązać ten problem, wprowadzono m.in. strukturę <b>wątków</b> .
  </p>
  <br>
  <br>
  <b style=COLOR:#3d85c6><font size=3>Watki</font></b><br>
  <hr size=2>
</div>
<br>
<div id=bt3z style=TEXT-ALIGN:left>
  <img src="images/dcjpvv6n_2327fbjnh8cb_b.png" style=HEIGHT:339px;WIDTH:500px><br>
  <br>
  <b>Wątek</b> (ang. <i>thread</i> ) jest definiowany często jako podstawowa jednostka wykorzystania procesora. Wątki można przedstawić jako fragmenty większej całości, jaką jest proces. Wątki współdzielą pewne zasoby charakterystyczne dla procesu tj.: sekcję kodu, sekcję danych, sygnały, otwarte pliki itp. Jeżeli teraz weźmiemy grupę wątków, z których każdy reprezentuje pewną sekwencję operacji do wykonania, i umieścimy je w ramach jednego procesu, możemy przełączać wątki nie przełączając procesu. Ilość informacji potrzebna do utrzymania wątku jest mniejsza ze względu na współdzielone dane między wątkami tego samego procesu, tym samym przełączanie kontekstu wątków jest znacznie szybsze od przełączania kontekstu procesów.<br>
  <br>
  <p>
    Omówione wątki funkcjonują <b>na</b> <b>poziomie</b> <b>jądra</b> (ang. <i>kernel</i> <i>mode</i> ) systemu operacyjnego; są nazywane zwany również <b>procesem</b> <b>lekkim</b> (ang. <i>lightweight</i> <i>process</i> – LWP). Obok nich mogą również występować <b>wątki</b> <b>poziomu</b> <b>użytkownika</b> . Wątki poziomu użytkownika działają całkowicie w przestrzeni użytkownika (ang. <i>user</i> <i>mode</i> ). Ich głównymi zaletami jest mały koszt tworzenia i usuwania oraz mały koszt przełączania kontekstu. Wadą jest blokada całego procesu w przypadku wywołań systemowych. W tym wypadku z pomocą przychodzą bardziej kosztowne w utrzymaniu wątki poziomu jądra.<br>
  </p>
  <p>
    <br>
  </p>
  <p>
    UWAGA. W terminologii procesów wyróżnia się specjalny przypadek jednowątkowego procesu tzw. <b>procesu</b> <b>ciężkiego</b> (ang. <i>heavyweight</i> <i>process</i> ).<br>
  </p>
  <p>
    <br>
  </p>
  <p>
    Minusem modelu przetwarzania z wątkami jest m.in. konieczność dbania programisty o bezpieczeństwo dostępu do dzielonych między wątki danych, co realizowane jest za pomocą semaforów itp. W zamian jednakże otrzymujemy wiele korzyści, a wśród nich m.in.: zwiększenie efektywności przy obsłudze wielu współbieżnych zadań, możliwość wykonywania równoległych wątków na wielu procesorach ze wspólną, dzieloną pamięcią.<br>
  </p>
  <p>
    <br>
  </p>
  <p>
    Wielowątkowość spowodowała również pewien przełom w podejściu do projektowania aplikacji. Zaczęto je m.in. dzielić na wiele mniejszych współpracujących ze sobą części. To z kolei uprościło i usystematyzowało niektóre aspekty budowania programów.
  </p>
  <br>
  <br>
  <b style=COLOR:#3d85c6><font size=3>Architektura klient-serwer</font></b><br>
  <hr size=2><a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-4-wyk-2.0-Slajd3 title=Sr-4-wyk-2.0-Slajd3> </a><br>
</div>
<div id=a81l style=TEXT-ALIGN:left>
  <img src="images/dcjpvv6n_2328fvhj6d6d_b.png" style=HEIGHT:341px;WIDTH:500px><br>
  <br>
  Architektura typu klient-serwer jest jedną z najpopularniejszych architektur stosowanych w systemach rozproszonych. Architektura ta w dużej mierze odnosi się do sposobu organizacji procesów w systemie.<br>
  <br>
  <p>
    Mamy tutaj więc wyróżnione dwie strony: klientów i serwery.<br>
  </p>
  <p>
    <br>
  </p>
  <p>
    Klient zazwyczaj zamawia pewną usługę u serwera, a ten ją wykonuje i być może odsyła klientowi wyniki. Należy zaznaczyć, że tego typu podejście jest w pewien sposób charakterystyczne również dla aplikacji nierozproszonych i wynika bezpośrednio z podziału funkcjonalnego oprogramowania. Ten wielopiętrowy model przetwarzania rozproszonego jest bezpośrednio konsekwencją tzw. <b>rozproszenia</b> <b>pionowego</b> , czyli umieszczenia różnych funkcjonalnie fragmentów systemu na różnych maszynach. Innym sposobem rozproszenia jest <b>rozproszenie</b> <b>poziome</b> , które polega na przetwarzaniu różnych fragmentów danych przez te same funkcjonalnie jednostki (serwery lub klienci umieszczeni na różnych maszynach). W przypadku braku serwera mówi się także o <b>rozproszeniu</b> <b>partnerskim</b> .
  </p>
  <br>
  <br>
  <b style=COLOR:#3d85c6><font size=3>Klienci wielowątkowi</font></b><br>
  <hr size=2><br>
  <div id=dabd style=TEXT-ALIGN:left>
    <img src="images/dcjpvv6n_2329qbfnscgv_b.png" style=HEIGHT:340px;WIDTH:500px><br>
    <br>
    Rozpatrzmy kilka przykładów aplikacji klienckich, w których realizacji zastosowano przetwarzanie wielowątkowe.
    <p>
      <br>
    </p>
    <p>
      Jedną z najczęściej stosowanych aplikacji są z pewnością przeglądarki stron WWW. Użytkownik często ma możliwość oglądania dokumentów mimo, że nie zostały jeszcze one całkowicie pobrane z odległych serwerów. Mamy tutaj m.in. wątki odpowiedzialne za interakcję użytkownika z przeglądarką oraz wątki odpowiedzialne za pobieranie brakujących elementów dokumentu.<br>
    </p>
    <p>
      <br>
    </p>
    <p>
      Kolejnym przykładem klienta wielowątkowego niech będzie aplikacja kliencka rozproszonego systemu plików. Ponieważ pliki, których potrzebuje klient mogą być umieszczone na różnych serwerach, może zajść konieczność wyszukania odpowiednich serwerów. Także w razie awarii klient musi mieć możliwość znalezienia odpowiedniego serwera. W przypadku aplikacji jednowątkowej klient takiego systemu musiałby po kolei weryfikować połączenia do serwerów, co jak nie trudno zauważyć, mogłoby zająć sporą ilość czasu. Utworzenie wielu wątków w tym przypadku zezwala na jednoczesne używanie kilku połączeń, a to z kolei znacząco przyśpiesza np. proces wyszukiwania odpowiedniego serwera do transferu danych. Dodatkowym elementem, jaki się tu pojawia, jest kwestia przezroczystość rozproszenia po stronie klienta, a tym samym pośrednio kwestia prostoty użytkowania takiej aplikacji.<br>
    </p>
    <p>
      <br>
    </p>
    <p>
      Ważną częścią klienta jest często interfejs użytkownika. Wielowątkowość pozwala m.in. na zmodularyzowanie jego budowy. Taka modularyzacja wiąże się również z możliwością wykonywania różnych modułów klienta na różnych maszynach np. w zależności od możliwości urządzenia, na którym pracuje klient.
    </p>
    <br>
    <br>
    <b style=COLOR:#3d85c6><font size=3>Wędrówka procesów w DEMOS/MP</font></b><hr size=2><br>
  </div>
  <div id=tg:w style=TEXT-ALIGN:left>
    <img src="images/dcjpvv6n_2330hhmvxjdt_b.png" style=HEIGHT:343px;WIDTH:500px><br>
    <br>
    <p>
      Wielowątkowość jest jednym z ważniejszych aspektów architektury serwerów. Nie trudno wyobrazić sobie serwer, który jednocześnie wykonuje kilka czynności naraz np.: komunikuje się z kilkoma innymi serwerami w poszukiwaniu aktualnych danych, obsługuje dużą liczbę klientów, a na dodatek wykonuje w tle pewne obliczenia lub inne operacje. Za przykład mogą tu posłużyć serwery obliczeniowe lub serwery służące do przechowywania i przetwarzania danych.<br>
    </p>
    <p>
      <br>
    </p>
    <p>
      Przyjrzyjmy się teraz bliżej budowie serwerów. Ze względu na sposób organizacji serwerów możemy wyróżnić następujące ich typy: <b>serwery</b> <b>iteracyjne</b> (ang. <i>iterative</i> <i>server</i> ) i <b>serwery</b> <b>współbieżne</b> (ang. <i>concurrent</i> <i>server</i> ).<br>
    </p>
    <p>
      <br>
    </p>
    <p>
      Serwer iteracyjny samodzielnie obsługuje zlecenia klientów zwracając im ewentualnie wyniki. Innymi słowy serwer zmuszony jest do obsługi zleceń jedno po drugim, przy czym zanim rozpocznie kolejne zadanie musi zakończyć wykonywanie poprzedniego.<br>
    </p>
    <p>
      <br>
    </p>
    <p>
      Serwer współbieżny pozbawiony jest niedogodności powodującej, że każde kolejne żądanie musi oczekiwać w kolejce do momentu gdy zostaną obsłużone poprzednie. W tym przypadku serwer po odebraniu zlecenia od klienta przekazuje wykonanie zlecenia innemu wątkowi lub procesowi. Po tym jak przekaże zlecenie może natychmiast przystąpić do obsługi innych zleceń. Z architekturą serwerów współbieżnych wiąże się m.in. kwestia miejsca kontaktowego z serwerem. Miejscem takim jest zazwyczaj pewien dobrze znany wszystkim klientom port (tzw. punkt końcowy – ang. <i>endpoint</i> ). Po skontaktowaniu się klienta przez taki port z serwerem klient otrzymuje np. nowy port do komunikacji z procesem obsługującym jego zlecenie, tym samym zwalnia punkt końcowy na rzecz nowych klientów serwera.
    </p>
    <p>
      Kolejnym kryterium według którego możemy dzielić serwery jest kwestia obsługi stanu. Wyróżniamy mianowicie: <b>serwery</b> <b>bezstanowe</b> (ang. <i>stateless</i> <i>server</i> ) oraz <b>serwery</b> <b>pełnostanowe</b> (ang. <i>stateful</i> <i>server</i> ).<br>
    </p>
    <p>
      <br>
    </p>
    <p>
      Serwer bezstanowy charakteryzuje się głównie tym, że nie przechowuje danych o swoich klientach. Również zmiana stanu samego serwera niekoniecznie wpływa na zmianę stanu jego klientów. Przykładem może być tu prosty serwer plików lub serwer sieci.<br>
    </p>
    <p>
      <br>
    </p>
    <p>
      Przeciwieństwem serwera bezstanowego jest serwer pełnostanowy, który przechowuje informacje o swoich klientach np. w celu odesłania im w przyszłości jakichś danych. Również tutaj za przykład może posłużyć rozproszony systemem plików, tym razem jednak taki, który przechowuje informacje o klientach w celu zapewnienia im w przyszłości szybszego dostępu do danych.<br>
    </p>
    <p>
      <br>
    </p>
    <p>
      Zasadniczą niedogodnością w przypadku serwerów pełnostanowych są awarie, które powodują utratę stanu i wymuszają konieczność jego odtwarzania.
    </p>
    <br>
    <br>
    <b style=COLOR:#3d85c6><font size=3>Serwery obiektowe</font></b><br>
    <hr size=2><br>
  </div>
</div>
<div id=xb6s style=TEXT-ALIGN:left>
  <img src="images/dcjpvv6n_2331cz4rqndp_b.png" style=HEIGHT:341px;WIDTH:500px><br>
  <br>
  Ogólnie rozumiany <b>serwer</b> <b>obiektowy</b> (ang. <i>object</i> <i>server</i> ) jest środowiskiem do przechowywania i zarządzania obiektami, także tymi rozproszonymi. Każdy obiekt posiada pewien kod, w postaci zaimplementowanych metod, oraz stan w postaci danych. Sposób zarządzania tymi obiema częściami zależy w dużej mierze od serwera obiektowego, którego implementacja określa np. to ile wątków ma działać w ramach jednego obiektu, czy dla każdego wywołania ma być używany osobny wątek, czy obiekty powinny mieć dostęp do wspólnych segmentów pamięci itp.<br>
  <br>
  <p>
    Najprostszym sposobem realizacji serwera obiektowego jest użycie jednego wątku sterowania. Innym podejściem jest zastosowanie kilku wątków, w ten sposób aby każdy obiekt miał własny wątek. W tym rozwiązaniu serwer po otrzymaniu zlecenia przekazuje je po prostu do odpowiedniego wątku, który jeśli jest zajęty w danej chwili, odkłada je na pewien czas do kolejki. Kolejnym podejściem jest zastosowanie osobnych wątków do każdego zamówienia. Wszystkie te rozwiązania sprowadzają się do wyboru pomiędzy tworzeniem wątków na żądanie a przechowywaniem pewnej liczby wątków.
  </p>
  <br>
  <br>
  <b style=COLOR:#3d85c6><font size=3>Adapter obiektów</font></b><br>
  <hr size=2><br>
</div>
<div id=sli4 style=TEXT-ALIGN:left>
  <img src="images/dcjpvv6n_2332gkvnkscx_b.png" style=HEIGHT:342px;WIDTH:500px>
</div>
<br>
Z serwerem obiektowym wiąże się pojęcie <b>adaptera</b> <b>obiektu</b> (ang. <i>object</i> <i>adapter</i> ). W skrócie można opisać go jako implementację pewnej <b>polityki</b> <b>uaktywniania</b> (ang. <i>activation</i> <i>policies</i> ) danego obiektu. Serwer obiektowy, w miarę potrzeby powinien mieć możliwość udostępniania różnej polityki uaktywnień wobec różnych obiektów, czyli powinien posiadać różne adaptery obiektów. Zamówienia, które przychodzą do takiego serwera są po prostu kierowane przez specjalny demultiplekser do odpowiedniego adaptera obiektu. Należy zaznaczyć, że adaptery obiektów nie muszą znać interfejsów obiektów, które obsługują.<br>
<br>
<br>
<b style=COLOR:#3d85c6><font size=3>Wędrówka procesów</font></b><br>
<hr size=2><br>
<div id=wk_x style=TEXT-ALIGN:left>
  <img src="images/dcjpvv6n_2333dncx9fgt_b.png" style=HEIGHT:341px;WIDTH:500px><br>
  <br>
  <b>Wędrówka</b> <b>kodu</b> (ang. <i>code</i> <i>migration</i> ), sprowadza się w dużej mierze do wędrówki pewnych danych. Jednakże, wędrówka kodu to niejednokrotnie coś więcej niż przesyłanie samych danych, a mianowicie związana z nią <b>wędrówka</b> <b>procesu</b> (migracja procesów – ang. <i>process</i> <i>migration</i> ). Ponieważ jak wiadomo, procesy mogą być aktywne i są z nimi związane pewne zasoby, problem wędrówki procesu jest o wiele bardziej skomplikowany niż wędrówka samych danych. Koszt takiej operacji jest zazwyczaj stosunkowy duży. Mimo to, właśnie efektywność jest główną przyczyną dla której wykonuje się przeniesienia procesów.<br>
  <br>
  <p>
    Jako przykład niech posłuży sieć komputerów, które wykonują pewne czasochłonne obliczenia. Część z nich może być mniej obciążona od innych. W celu poprawy globalnej efektywności przetwarzania przenosimy część obliczeń z komputerów bardziej obciążonych na te mniej obciążone. Praktyczna realizacja tej koncepcji wymaga jednak odpowiedzi na wiele szczegółowych pytań. Jak stwierdzić które z komputerów są mniej obciążone? Jaki jest algorytm według, którego procesy są przydzielane lub przenoszone na odpowiednie komputery? Co zrobić gdy środowisko maszyn jest heterogeniczne? Tymi i innymi kwestiami związanymi z wędrówką procesów zajmiemy się w dalszej części wykładu.
  </p>
  <br>
  <br>
  <b style=COLOR:#3d85c6><font size=3>Proste przykłady wędrówki kodu</font></b><br>
  <hr size=2><br>
</div>
<div id=b-sz style=TEXT-ALIGN:left>
  <img src="images/dcjpvv6n_2334d2rgp9c7_b.png" style=HEIGHT:342px;WIDTH:500px>
</div>
<br>
Jednym z bardziej popularnych przykładów wędrówki kodu jest przenoszenie części operacji ze strony serwera na stronę klienta np. weryfikacja formularzy wypełnianych przez użytkownika lub inne operacje na danych, które skutkują ich szybszym przesyłaniem do serwera. Takie operacje, nawet jeżeli proste, mogą często w znaczący sposób odciążyć serwery, a tym samym znacząco zwiększyć ich efektywność.<br>
<br>
<p>
  Innym przykładem wykorzystania migracji procesów są mobilne programy, które poprzez zwielokrotnienie się na wielu komputerach mogą przyspieszyć wykonywanie rozległych operacji.<br>
</p>
<p>
  <br>
</p>
<p>
  Istotną cechą wędrówki kodu jest jej elastyczność i możliwość dynamicznej konfiguracji. Za przykład może tu posłużyć dostarczanie kodu do klienta w miarę potrzeby, tak aby nie musiał on wcześniej instalować wszystkich niezbędnych aplikacji. Implementacją takiego modelu są m.in. powszechnie używane aplety zrealizowane w środowisku Java.
</p>
<br>
<br>
<b style=COLOR:#3d85c6><font size=3>Model wędrówki procesów</font></b><br>
<hr size=2><br>
<div id=rwz9 style=TEXT-ALIGN:left>
  <img src="images/dcjpvv6n_2335ch8q9qg6_b.png" style=HEIGHT:342px;WIDTH:500px><br>
  <br>
  Operacja przenoszenia procesu z jednej maszyny na drugą może przybierać wiele postaci. Oprócz wędrówki kodu możemy mieć tu do czynienia z koniecznością przeniesienia stanu procesu, który jest w trakcie wykonywania. Dla uproszczenia rozważań o modelach załóżmy, że każdy proces składa się z trzech segmentów: segmentu kodu, segmentu zasobów oraz segmentu wykonania (ang. <i>execution</i> <i>segment</i> ), który przechowuje dane o bieżącym stanie procesu.<br>
  <br>
  <p>
    W najprostszym przypadku będziemy mieli do czynienia z <b>przenośnością</b> <b>słabą</b> (ang. <i>weak</i> <i>mobility</i> ). W tym przypadku przesyłany jest tylko segment kodu. Jeżeli dodamy tego możliwość przesyłania segmentu wykonania uzyskamy tzw. <b>przenośność</b> <b>silną</b> (ang. <i>strong</i> <i>mobility</i> ). Przenośność silna jest ogólniejsza od słabej i pozwala na przenoszenie procesów w trakcie ich wykonywania. Wadą przenośności silnej jest jednak jej większa złożoność.<br>
  </p>
  <p>
    <br>
  </p>
  <p>
    Przenośność słabą można jeszcze rozróżnić w zależności od tego czy w celu wykonania przesłanego kodu uruchamiany jest nowy proces na maszynie docelowej, czy też kod ten wykonywany jest w ramach pewnego procesu docelowego.<br>
  </p>
  <p>
    <br>
  </p>
  <p>
    W wypadku przenośności silnej wyróżnia się metodę klonowania procesów, która polega na skopiowaniu działającego programu na docelową maszynę w taki sposób, że oryginał i jego kopia działają równolegle.<br>
  </p>
  <p>
    <br>
  </p>
  <p>
    Kolejną kwestią wymagającą rozpatrzenia jest wybór inicjatora wędrówki. Jeżeli jest to pierwotny posiadacz procesu, mówimy o <b>wędrówce</b> <b>inicjowanej</b> <b>przez</b> <b>nadawcę</b> (ang. <i>sender-initiated</i> ). Gdy natomiast inicjatywę podejmuje maszyna docelowa, na której ma się wykonywać proces, mamy do czynienia z <b>wędrówką</b> <b>inicjowaną</b> <b>przez</b> <b>odbiorcę</b> (ang. <i>receiver-initiated</i> ).
  </p>
  <br>
  <br>
  <b style=COLOR:#3d85c6><font size=3>Wiązanie zasobów lokalnych</font></b><br>
  <hr size=2><br>
  <div id=kshx style=TEXT-ALIGN:left>
    <img src="images/dcjpvv6n_2336kq97nccb_b.png" style=HEIGHT:341px;WIDTH:500px><br>
    <br>
    Wraz z wędrówką procesu pojawia się problem zarządzania zasobami lokalnymi, z których korzysta przenoszony proces. Sposób postępowania z zasobami lokalnymi zależy od kilku czynników. Jednym z nich jest sposób w jaki proces jest związany z danym zasobem. Wyróżniono zasadniczo trzy sposoby wiązania zasobów: <b>wiązanie</b> <b>przez</b> <b>identyfikator</b> (ang. <i>binding</i> <i>by</i> <i>identifier</i> ), <b>wiązanie</b> <b>przez</b> <b>wartość</b> (ang. <i>binding</i> <i>by</i> <i>value</i> ) i <b>wiązanie</b> <b>przez</b> <b>typ</b> (ang. <i>binding</i> <i>by</i> <i>type</i> ).<br>
    <br>
    <p>
      Proces, który odwołuje się do zasobu przez identyfikator oczekuje konkretnego zasobu o danym identyfikatorze, czyli np. adresie internetowym. Jest to najmocniejsza forma wiązania. Słabszą formą związania zasobu jest wiązanie przez wartość. Taki typ wiązania powoduje, że proces odwołuje się do wartości zasobu, a nie do konkretnego zasobu. Ostatnim, najmniej wymagającym typem wiązania, jest wiązanie przez typ, w którym wymaga się dostępu do zasobu o określonym typie .
    </p>
    <br>
    <br>
    <b style=COLOR:#3d85c6><font size=3>Wiązanie zasobów z maszyną</font></b><br>
    <hr size=2><br>
    <div id=sh95 style=TEXT-ALIGN:left>
      <img src="images/dcjpvv6n_23373swb7pdj_b.png" style=HEIGHT:342px;WIDTH:500px><br>
      <br>
      Wraz z wędrówką procesu często występuje konieczność zmiany odniesienia do zasobów. Rodzaj wiązania pozostaje zawsze ten sam. To w jaki sposób zostanie zmienione odniesienie do danego zasobu, zależy od sposobu jego powiązania z konkretną maszyną.<br>
      <br>
      <p>
        <b>Zasoby</b> <b>niepołączone</b> (ang. <i>unattached</i> <i>resources</i> ) można w stosunkowo łatwy sposób przenosić między maszynami np. pliki z danymi. Bardziej kłopotliwymi zasobami są <b>zasoby</b> <b>umocowane</b> (ang. <i>fastened</i> <i>resources</i> ). Ich przeniesienie jest możliwe, aczkolwiek koszt jest nieraz na tyle wysoki, że praktycznie jest to nieopłacalne. W końcu mamy <b>zasoby</b> <b>nieruchome</b> (ang. <i>fixed</i> <i>resources</i> ), których przeniesienie jest niemożliwe. Są to m.in. urządzenia do wykonywania pewnego typu zadań np. drukarka, ploter.<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        Podczas wędrówki procesu możemy postąpić z jego zasobami w różny sposób, w zależności od rodzaju zasobu. Jeżeli zasób jest niepołączony, to zazwyczaj jest on przenoszony lub kopiowany, jeżeli nie jest to wiązanie przez identyfikator. Zasoby związane przez typ można związać z reguły na nowo z zasobem dostępnym lokalnie, jeżeli taki jest oczywiście dostępny. W przypadku zasobów nieruchomych często jedyną możliwością są globalne odniesienia. Zasoby wiązane przez wartość dają również możliwość skopiowania samej wartości, chyba że mamy do czynienia z zasobami nieruchomymi.
      </p>
      <br>
      <br>
      <b style=COLOR:#3d85c6><font size=3>Wędrówka w systemach heterogenicznych</font></b><br>
      <hr size=2><br>
      <div id=gmak style=TEXT-ALIGN:left>
        <img src="images/dcjpvv6n_2338gddcjtqg_b.png" style=HEIGHT:341px;WIDTH:500px><br>
        <br>
        W przypadku systemów rozproszonych istotnym czynnikiem przy ich projektowaniu jest heterogeniczność.<br>
        <br>
        <p>
          Szczególnie widać to właśnie w przypadku procesów i ich wędrówki. Dopóki rozpatrujemy identyczne maszyny, czyli mamy do czynienia ze środowiskiem homogenicznym, dopóty nie istnieje wiele problemów związanych z różnicami wewnątrz środowiska maszyn i oprogramowania.<br>
        </p>
        <p>
          <br>
        </p>
        <p>
          Możliwość wykonania identycznego kodu na różnych typach maszyn i właściwego przechowywania stanu procesu są kluczowe dla poprawnego wykonania operacji przeniesienia procesu. Stopień komplikacji wędrówki procesu w systemie zależy oczywiście od typu wędrówki. Jeżeli jest to przenośność słaba, problem sprowadza się do wygenerowania kodu dla odpowiednich typów platform. Nie ma tu natomiast przeniesienia segmentu wykonania, który może znacząco się różnić w zależności od architektury maszyny.<br>
        </p>
        <p>
          <br>
        </p>
        <p>
          Przykładowym rozwiązaniem, które zastosowano m.in. dla języka Java jest zezwolenie na wędrówkę procesu tylko w określonych punktach jego wykonywania np. przy wywoływaniu metody, wtedy też aktualizowany jest tzw. <b>stos</b> <b>wędrówki</b> (ang. <i>migration</i> <i>stack</i> ). Stos wędrówki jest niczym innym jak kopią stosu programu ale przechowywaną w sposób niezależny od maszyny.<br>
        </p>
        <p>
          <br>
        </p>
        <p>
          Za każdym razem kiedy proces wchodzi do podprogramu i z niego wychodzi odpowiednie dane ze stosu, identyfikator wywołanego podprogramu oraz etykieta powrotu (adres od którego należy kontynuować przetwarzanie po powrocie z podprogramu) są <b>przetaczane</b> (ang. <i>marshaled</i> ) i odkładane na stosie wędrówki. Stos wędrówki jest w razie wędrówki procesu przenoszony na maszynę docelową i tam <b>odwrotnie</b> <b>przetaczany</b> (ang. <i>unmarshaled</i> ), tak aby można było odtworzyć stos fazy wykonywania.
        </p>
        <br>
        <br>
        <b style=COLOR:#3d85c6><font size=3>Komunikaty a wędrówka procesów</font></b><br>
        <hr size=2><br>
        <div id=m1qh style=TEXT-ALIGN:left>
          <img src="images/dcjpvv6n_2339c9k8w9c6_b.png" style=HEIGHT:341px;WIDTH:500px><br>
          <br>
          Podczas wędrówki procesu pojawia się pewna trudność w postaci stanu komunikacji przenoszonego procesu. Poza tym nasuwa się również pytanie, co zrobić z przyszłymi komunikatami, które będą nadchodzić do wspomnianego procesu.<br>
          <br>
          <p>
            Odpowiedzią na te problemy mogą być trzy następujące rozwiązania: <b>przekierowywanie</b> <b>komunikatów</b> (ang. <i>message</i> <i>redirection</i> ), <b>zapobieganie</b> <b>utracie</b> <b>komunikatów</b> (ang. <i>message</i> <i>loss</i> <i>prevention</i> ) oraz <b>odzyskiwanie</b> <b>utraconych</b> <b>komunikatów</b> (ang. <i>message</i> <i>loss</i> <i>recovery</i> ).<br>
          </p>
          <p>
            <br>
          </p>
          <p>
            Pierwsze z wymienionych podejść, czyli przekierowywanie komunikatów działa w ten sposób, że komputer, z którego proces wywędrował musi zapamiętać wszystkie możliwe źródła komunikatów dla tego procesu. Ponadto maszyna źródłowa musi również znać adres docelowej maszyny, do której odbyła się wędrówka. Z kolei procesy-nadawcy niekoniecznie są informowani o fakcie wędrówki i mogą wysyłać komunikaty do starego miejsca procesu. Jeżeli w trakcie wędrówki procesu przychodziły komunikaty, są one zapamiętywane w starym miejscu i dostarczane do procesu-odbiorcy po ukończeniu operacji wędrówki. Wadą tego podejścia jest łańcuch pośredników rosnący w miarę, jak proces migruje na kolejne maszyny.<br>
          </p>
          <p>
            <br>
          </p>
          <p>
            W podejściu polegającym na zapobieganiu utracie wiadomości proces który zamierza wędrować powiadamia o tym wszystkie procesy, z którymi utrzymuje komunikację, tak aby te mogły po ukończeniu komunikować się z nim bezpośrednio. W przeciwieństwie do poprzedniej metody unika się tu pośredników w komunikacji, dzięki czemu ruch w systemie jest mniejszy.<br>
          </p>
          <p>
            <br>
          </p>
          <p>
            W ostatniej metodzie polegająca na odzyskiwaniu utraconych komunikatów, proces podlegający wędrówce nie wysyła do procesów, z którymi się komunikuje żadnych informacji o tym fakcie. Wszystkie wiadomości, które nadchodzą podczas procesu migracji są po prostu ignorowane i tracone. Proces po zakończeniu migracji nawiązuje ponownie komunikację z procesami, z którymi ją wcześniej utrzymywał i rozpoczynany jest proces odzyskiwania utraconych komunikatów. Metoda ta stosowana jest często w systemach, gdzie liczy się czas migracji procesu, gdyż jest ona stosunkowo szybka i prosta.
          </p>
          <br>
          <br>
          <b style=COLOR:#3d85c6><font size=3>Wędrówka procesów w DEMOS/MP</font></b><br>
          <hr size=2><br>
          <div id=er42 style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2340gxps83ht_b.png" style=HEIGHT:343px;WIDTH:500px><br>
            <br>
            W tej części zaprezentujemy przykładowy mechanizm migracji procesów zastosowany w rozproszonym systemie operacyjnym DEMOS/MP. Przykład ten zilustruje w skrócie zagadnienia jakie wiążą się z wędrówką procesów.<br>
            <br>
            <p>
              Operacja wędrówki procesu w systemie DEMOS/MP składa się z dwóch części: negocjacji oraz przemieszczenia procesu.<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              W fazie negocjacji komputer źródłowy wysyła propozycję wędrówki procesu do komputera docelowego. Wraz z propozycją wędrują również informacje niezbędne do podjęcia wędrówki. Jeżeli komputer docelowy ma wystarczającą ilość zasobów odsyła do komputera, który przysłał ofertę, odpowiedź z akceptacją wędrówki. W przeciwnym wypadku komputer źródłowy otrzymuje odmowę i trzeba na nowo zaplanować całą operację.
            </p>
            <br>
            <br>
            <b style=COLOR:#3d85c6><font size=3>Ilustracja wędrówki procesów w DEMOS/MP</font></b><br>
            <hr size=2><br>
          </div>
          <div id=l7:y style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2341dsrjf8fc_b.png" style=HEIGHT:342px;WIDTH:500px><br>
            <br>
            W drugiej fazie, przemieszczania procesu następuje kilka mniejszych kroków.<br>
            <br>
            <p>
              Gdy już wybrany został proces do migracji i wiadomo gdzie ma się znaleźć, następuje jego oznaczenie jako procesu do migracji. To skutkuje m.in. tym, że proces taki usuwany jest z kolejki procesów do uruchomienia. Wiadomości, które przychodzą do procesu nadal będą odbierane i umieszczane w jego kolejce komunikatów.<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              W drugim kroku do komputera docelowego, a dokładniej do jądra systemu operacyjnego, który nim zarządza, zostaje wysłana wiadomość z żądaniem, aby przemieścić proces. Wiadomość ta zawiera wszystkie informacje potrzebne do wędrówki procesu: rozmiar i lokalizację kodu oraz dane dotyczące stanu itp.<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              Następnie zostaje utworzony specjalny proces na maszynie docelowej. Proces ten nie posiada jeszcze żadnego stanu. W międzyczasie rezerwowane są wymagane przez proces zasoby.<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              Skoro na komputerze docelowym jest już pewien proces zostaje na jego miejsce skopiowany stan oryginalnego procesu (przeniesienie odpowiednich danych).<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              Po tym zostaje ostatecznie przeniesiony cały program w postaci kodu, danych oraz stosu.<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              Kiedy kontrola trafi z powrotem do jądra systemu maszyny źródłowej i zostanie potwierdzony fakt przeniesienia procesu, stary komputer przesyła do nowego wszystkie wiadomości, które trzymał w kolejce od momentu rozpoczęcia wędrówki. W trakcie tej fazy komputer źródłowy zapamiętuje także informacje o nowym miejscu pobytu procesu.<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              W przedostatnim kroku fazy przenoszenia procesu jądro systemowe na maszynie źródłowej czyści stan oryginalnego procesu pozostawiając tylko wcześniej wspomniany adres maszyny docelowej. Adres ten będzie służył w przyszłości do komunikacji z przeniesionym procesem.<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              Na końcu kontrola ostatecznie wraca do maszyny docelowej, a nowy proces zostaje przywrócony do stanu sprzed momentu wędrówki.
            </p>
            <br>
            <br>
            <b style=COLOR:#3d85c6><font size=3>Agenci programowi</font></b><br>
            <hr size=2><br>
          </div>
          <div id=wzy0 style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2342dq9xscfw_b.png" style=HEIGHT:340px;WIDTH:500px><br>
            <br>
            <p>
              Mimo braku precyzyjnej definicji <b>agenta</b> <b>programowego</b> (ang. <i>software</i> <i>agent</i> ), można go opisać jako pewne rozszerzenie pojęcia procesu, w tym sensie, że jest on zdolny do samodzielnego działania; jest autonomiczny i potrafi się również komunikować z innymi agentami. W miarę rozwoju badań nad agentami programowymi wyróżniono kilka ich typów.<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              <b>Agenci</b> <b>współpracujący</b> (ang. <i>collaborative</i> <i>agent</i> ) charakteryzują się tym, że dążą do osiągnięcia pewnego wspólnego celu poprzez współpracę ze sobą.<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              <b>Agenci</b> <b>ruchomi</b> (ang. <i>mobile</i> <i>agents</i> ) potrafią z kolei się przemieszczać między różnymi maszynami, zbierając np. różne dane.
            </p>
            <p>
              <b>Agenci</b> <b>interfejsu</b> (ang. <i>interface</i> <i>agents</i> ) pomagają użytkownikom w używaniu różnych aplikacji, często ucząc się przy tym w celu poprawienia przyszłego działania.<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              Ostatnią przedstawioną tu klasą agentów są <b>agenci</b> <b>informacji</b> (ang. <i>information</i> <i>agents</i> ). Są oni odpowiedzialni za zarządzanie informacjami np. filtrowanie.<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              Ważnym elementem działania agentów programowych jest sposób ich komunikacji. Do tego celu służy tzw. <b>kanał</b> <b>komunikacji</b> <b>agentów</b> (ang. <i>agent</i> <i>communication</i> <i>channel</i> – ACC). ACC jest między innymi odpowiedzialne za niezawodność komunikacji i porządek komunikatów. Wraz z ACC pojawia się również <b>język</b> <b>komunikacji</b> <b>agentów</b> (ang. <i>agent</i> <i>communication</i> <i>language</i> – ACL). Język ten określa pewien standard wymiany informacji między agentami, protokół. Istotne w przypadku ACL jest rozdzielenie w komunikacie dwóch składników: jego celu i treści. Wyróżnia się pewną skończoną liczbę celów, na które agent-odbiorca może zareagować. Przykładowymi celami są zamówienie jakiegoś działania, pytanie o jakiś obiekt lub dostarczenie jakiejś oferty.
            </p>
            <br>
            <br>
            <b style=COLOR:#3d85c6><font size=3>Szeregowanie procesów</font></b><br>
            <hr size=2><br>
            <div id=y.d1 style=TEXT-ALIGN:left>
              <img src="images/dcjpvv6n_2343f2p85fhn_b.png" style=HEIGHT:341px;WIDTH:500px><br>
              <br>
              <b>Szeregowanie</b> <b>procesów</b> (ang. <i>process</i> <i>scheduling</i> ) jest integralną częścią zarządzania procesami. Ponieważ procesy możemy traktować jako pewne zasoby, również zarządzanie procesami możemy zaklasyfikować jako szczególny rodzaj zarządzania zasobami. Zrozumienie niektórych aspektów zarządzania zasobami pozwoli z pewnością uzasadnić potrzebę takich operacji jak wędrówka lub zdalne wykonywanie procesów.<br>
              <br>
              <p>
                Szeregowanie procesów związane jest z polityką odpowiedzialną za podejmowanie decyzji, od których zależą: lokalne uszeregowanie procesów (tj. uszeregowanie w ramach pojedynczego procesora) oraz strategia rozproszenia obciążenia pomiędzy różne maszyny obecne w systemie. Nie będziemy podczas tego wykładu zagłębiać się w problematykę lokalnego szeregowania procesów, a skupimy się na szeregowaniu globalnym. Należy zaznaczyć, że samo szeregowanie lokalne nie jest w stanie zagwarantować uszeregowania optymalnego z punktu widzenia globalnego systemu. Do rozwiązania problemów globalnego szeregowania procesów stosuje się zasadniczo dwa typy algorytmów. Mianowicie wyróżniamy algorytmy <b>podziału</b> <b>obciążenia</b> (ang. <i>load</i> <i>sharing</i> ) oraz algorytmy <b>równoważenia</b> <b>obciążenia</b> (ang. <i>load</i> <i>balancing</i> ). Warto podkreślić, iż oba podejścia zakładają wędrówkę procesów.
              </p>
              <br>
              <br>
              <b style=COLOR:#3d85c6><font size=3>Zdalne operacje na procesach</font></b><br>
              <hr size=2><br>
              <div id=obzd style=TEXT-ALIGN:left>
                <img src="images/dcjpvv6n_2344ftvtv4f2_b.png" style=HEIGHT:342px;WIDTH:500px><br>
                <br>
                W przypadku systemów scentralizowanych dostępny jest zawsze pewien podstawowy zestaw operacji, które można wykonać na procesach. Za pomocą tych operacji możemy wpływać na stan procesów. Wśród nich znajdziemy operacje takie jak utworzenie nowego procesu, zakończenie procesu, zawieszenie procesu, wznowienie procesu itp.<br>
                <br>
                <p>
                  Rozproszone systemy operacyjne ze względu na swoją architekturę, oprócz lokalnych operacji powinny posiadać dodatkowy zestaw w postaci <b>zdalnych</b> <b>operacji</b> (ang. <i>remote</i> <i>operations</i> ) na procesach. Są to m.in. utworzenie, zakończenie, zawieszenie wykonywania, wznowienie, zdalne uruchomienie procesu, migracja procesu, tworzenie połączeń komunikacyjnych.<br>
                </p>
                <p>
                  <br>
                </p>
                <p>
                  W idealnym przypadku wszystkie te operacje powinny być niewidoczne dla użytkownika.
                </p>
                <br>
                <br>
                <b style=COLOR:#3d85c6><font size=3>Zdalne wykonywanie procesów</font></b><br>
                <hr size=2><br>
              </div>
              <div id=cbdx style=TEXT-ALIGN:left>
                <img src="images/dcjpvv6n_2345dvq75tgx_b.png" style=HEIGHT:341px;WIDTH:500px><br>
                <br>
                <b>Zdalne</b> <b>wykonywanie</b> <b>procesów</b> (ang. <i>remote</i> <i>execution</i> ) i wędrówka procesów są dwoma podstawowymi mechanizmami używanym przy szeregowaniu zadań. Główną cechą, która odróżnia zdalne wykonywanie procesu od wędrówki procesów jest to, że proces uruchomiony zdalnie nie może już migrować.<br>
                <br>
                <p>
                  Szeregowanie procesów spełnia w kontekście operacji zdalnego wykonywania procesów kilka zadań: określa <b>politykę</b> <b>transferu</b> <b>procesu</b> (ang. <i>transfer</i> <i>policy</i> ) w celu zadecydowania czy proces ma być uruchomiony zdalnie czy lokalnie, określa <b>politykę</b> <b>wyboru</b> <b>procesu</b> (ang. <i>selection</i> <i>policy</i> ) aby zadecydować który proces powinien być przeniesiony oraz określa <b>politykę</b> <b>wyboru</b> <b>miejsca</b> (ang. <i>location</i> <i>policy</i> ), w którym ma być uruchomiony wybrany proces.
                </p>
                <br>
                <br>
                <b style=COLOR:#3d85c6><font size=3>Podział obciążenia</font></b><br>
                <hr size=2>
              </div>
              <br>
              <div id=it3k style=TEXT-ALIGN:left>
                <img src="images/dcjpvv6n_2346fdc4jxrz_b.png" style=HEIGHT:342px;WIDTH:500px><br>
                <br>
                <b>Podział</b> <b>obciążenia</b> jest metodą, która pozwala na wykorzystanie mocy obliczeniowej maszyn, które w danej chwili nic nie przetwarzają. Algorytmy dokonujące podziału obciążenia zwiększają efektywność tylko lokalnie, wewnątrz pewnej grupy użytkowników i ich procesów. Metoda ta bazuje głownie na migracji procesów na bezczynne maszyny.<br>
                <br>
                <p>
                  Algorytm podziału obciążeń ma do rozwiązania przede wszystkim dwie kwestie. Po pierwsze, kiedy przeprowadzić wędrówkę procesu na zdalną bezczynną maszynę. Po drugie, jak znaleźć zdalny bezczynny procesor. W pierwszym przypadku odpowiedź wydaje się stosunkowo prosta: kiedy moc obliczeniowa maszyny przestaje wystarczać potrzebom procesów użytkownika. Natomiast odpowiedzi na drugie pytanie może być wiele m.in.: można skorzystać ze specjalnego serwera, który zbiera informacje o wolnych zasobach, można też skorzystać z mechanizmu komunikacji grupowej do rozgłaszania informacji o bezczynnych procesorach, w końcu można np. skorzystać z informacji przechowywanych lokalnie.<br>
                </p>
                <p>
                  <br>
                </p>
                <p>
                  Systemy, które używają podziału obciążenia mogą korzystać z różnych struktur komunikacyjnych do szeregowania procesów.<br>
                </p>
                <p>
                  <br>
                </p>
                <p>
                  W przypadku użycia scentralizowanej struktury występuje pewna wyróżniona maszyna, która zbiera informacje o bezczynnych komputerach i na tej podstawie może szeregować procesy. Wadą takiego podejścia są oczywiście podatność na awarię oraz trudność w śledzeniu stanu wszystkich procesorów przez jedną maszynę.<br>
                </p>
                <p>
                  <br>
                </p>
                <p>
                  Zamiast scentralizowanej struktury można użyć rozproszonej. Mamy wtedy kilka maszyn, z których każda stara się znaleźć odpowiednie miejsca do wykonania swoich procesów. W tym wypadku niezbędna staje się synchronizacja między maszynami. Rozproszone podejście do podziału obciążeń likwiduje wspomniane wady scentralizowanego algorytmu, jakkolwiek jest bardziej czasochłonne ze względu na koordynację działań komputerów, biorących udział w operacji.
                </p>
                <br>
                <br>
                <b style=COLOR:#3d85c6><font size=3>Hierarchiczny algorytm podziału obciążenia</font></b><br>
                <hr size=2><br>
              </div>
              <div id=zc3h style=TEXT-ALIGN:left>
                <img src="images/dcjpvv6n_2347f686spd4_b.png" style=HEIGHT:344px;WIDTH:500px><br>
                <br>
                W prezentowanym tutaj algorytmie wykorzystuje się hierarchię procesorów w postaci ściętego drzewa (ang. <i>truncated</i> <i>tree</i> ). Na najniższym poziomie drzewa wyróżnia się procesory, które są robotnikami. Na wyższym poziomie znajdują się procesory-zarządcy, którzy mają pod sobą robotników. Na najwyższym poziomie są z kolei procesory odpowiedzialne za globalną alokację.
                <p>
                  <br>
                </p>
                <p>
                  Alokacja procesorów w momencie, gdy pojawi się praca wymagająca <i>m</i> procesów przebiega następująco. System zostaje powiadomiony o potrzebie zaalokowania <i>m</i> procesorów. Każdy procesor-zarządca zna w przybliżeniu liczbę robotników, którymi zarządza. Jeśli liczba wolnych robotników-procesorów jest wystarczająca (większa od <i>m</i> ), to procesory te zostają zarezerwowane i praca może zostać wykonana. W przeciwnym wypadku, kiedy zarządca nie ma takiej liczby robotników, przekazuje żądanie w górę hierarchii zarządców do momentu napotkania najwyższego węzła-szefa. Jeżeli taki węzeł stwierdzi, że nie ma on wystarczającej liczby procesorów, to przekazuje żądanie do swoich sąsiadów na tym samym poziomie drzewa.
                </p>
                <br>
                <br>
                <b style=COLOR:#3d85c6><font size=3>Algorytm hierarchiczny - przykład</font></b><br>
                <hr size=2><br>
              </div>
              <div id=ua.r style=TEXT-ALIGN:left>
                <img src="images/dcjpvv6n_2348f9wsz8vw_b.png" style=HEIGHT:341px;WIDTH:500px><br>
                <br>
                W zilustrowanym przykładzie wystąpiło zadanie, które wymaga 4 procesorów. Niestety zarządca procesora, który jest inicjatorem zadania (oznaczony żółtym kolorem) nie ma pod sobą wystarczającej liczby wolnych procesorów. Zleca więc zadanie zarządcy, który jest wyżej w hierarchii od niego i który to zajmuje się globalną alokacją. Ten niestety też nie ma pod sobą wystarczającej liczby wolnych procesorów, pyta więc kolejno innych globalnych zarządców do momentu aż znajduje zarządcę z odpowiednią liczbą wolnych procesorów. Wtedy rezerwowane są znalezione wolne procesory i zadanie może być wykonane.<br>
                <br>
                <br>
                <b style=COLOR:#3d85c6><font size=3>Pierścieniowy algorytm podziału obciążenia</font></b><br>
                <hr size=2><br>
                <div id=iq1h style=TEXT-ALIGN:left>
                  <img src="images/dcjpvv6n_2349hkfwvgc3_b.png" style=HEIGHT:340px;WIDTH:500px><br>
                  <br>
                  Algorytm ten oparty jest na pierścieniowej strukturze procesorów. Jeżeli pojawi się zadanie wymagające <i>m</i> procesów, system musi zarezerwować w tym celu <i>m</i> procesorów. Po pierścieniu procesorów krąży tzw. żeton (ang<i>.</i> <i>token</i> ). W momencie gdy procesor, która ma zadanie do wykonania, ma żeton, może rozpocząć poszukiwanie bezczynnych procesorów. W pierwszym kroku zarządca (procesor, który ma żeton) rozsyła komunikaty do innych węzłów aby dowiedzieć się, czy są one dostępne. Jeżeli jakiś węzeł jest dostępny, odsyła informację do zarządcy, a ten rezerwuje dany procesor. Procesor jest zwalniany jeżeli w określonym czasie nie otrzyma żądania wykonania procesu. Ponadto jeśli liczba dostępnych procesorów jest zbyt mała dla zarządcy, są one zwalniane. Po tych czynnościach zarządca przekazuje żeton do swojego następnika w pierścieniu. Gdy poszukiwanie się powidło i zarządca ma wystarczającą liczbę dostępnych węzłów, rozdziela między nie odpowiednio procesy, a po zakończeniu zadania wszystkie procesory są zwalniane.<br>
                  <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-4-wyk-2.0-Slajd25 title=Sr-4-wyk-2.0-Slajd25> </a><br>
                </div>
                <br>
                <b style=COLOR:#3d85c6><font size=3>Podział obciążenia w systemie Condor</font></b><br>
                <hr size=2>
              </div>
              <br>
              <div id=yveo style=TEXT-ALIGN:left>
                <img src="images/dcjpvv6n_2350dtqn98ck_b.png" style=HEIGHT:343px;WIDTH:500px><br>
                <br>
                Condor jest systemem służącym do szeregowania zadań, który umożliwia użycie bezczynnych węzłów. Algorytm szeregujący procesy działa następująco. Każdy komputer ma swój indeks <i>i</i> , który początkowo jest równy zero. Indeks każdego komputera jest aktualizowany w następujący sposób: gdy przydzielone zostają mu zdalne zasoby obliczeniowe, jego indeks jest powiększany, natomiast gdy takie zasoby na skutek jego żądania nie zostają mu przydzielone, jego indeks maleje. W systemie znajduje się centralny koordynator, który przelicza priorytety każdego komputera używając wspomnianych indeksów. Zadanie ze stacji <i>i</i> ma wywłaszczający priorytet w stosunku do zadania ze stacji <i>j</i> , jeżeli indeks stacji <i>i</i> jest mniejszy od indeksu stacji <i>j</i> . Następnie koordynator sprawdza, czy jakiś komputer ma nowe zadania do zdalnego wykonania. Jeśli komputer z wyższym priorytetem ma zadanie do wykonania, ale nie ma wolnych innych komputerów, koordynator wywłaszcza zdalnie uruchomioną pracę na stacji o niższym priorytecie i tworzy <b>punkt</b> <b>kontrolny</b> przerwanego zadania (ang. <i>checkpoint</i> ). Punkt kontrolny jest operacją zapamiętania stanu procesu tak aby można go było kontynuować w przyszłości. Po tej operacji komputer z wyższym priorytetem uruchamia swoje zadanie na nowo dostępnym komputerze.<br>
                <br>
                <br>
                <b style=COLOR:#3d85c6><font size=3>Równoważenie obciążenia</font></b><hr size=2><br>
                <div id=qjr4 style=TEXT-ALIGN:left>
                  <img src="images/dcjpvv6n_2351h25n4cd9_b.png" style=HEIGHT:341px;WIDTH:500px><br>
                  <br>
                  Równoważenie obciążenia jest stosunkowo rozległą dziedziną związaną m.in. z zarządzaniem procesami, dlatego tutaj skupimy się na kluczowych jego własnościach. Dalej przedstawimy również kilka przykładów algorytmów równoważenia obciążenia.<br>
                  <br>
                  <p>
                    Głównym zadaniem równoważenia obciążenia jest uszeregowanie procesów w systemie rozproszonym w taki sposób, aby zrównoważyć w nim obciążenie pracą. Do tego celu wykorzystywana jest m.in. wcześniej zaprezentowana wędrówka procesów. W przeciwieństwie do podziału obciążenia w tym przypadku nie ma wymogu, aby procesory, na które migrowane są zadania były wcześniej bezczynne. Procesory mogą być częściowo obciążone, a mimo to nadal są brane pod uwagę przy wędrówce procesów.<br>
                  </p>
                  <p>
                    <br>
                  </p>
                  <p>
                    W przypadku algorytmów równoważenia obciążenia można wyróżnić grupę komponentów, z których każdy jest odpowiedzialny za pewien element ich polityki. Kilka takich komponentów zostało zaprezentowanych przy okazji omawiania zdalnego uruchamiania procesów. Były to: polityka transferu procesu, polityka wyboru procesu oraz polityka wyboru miejsca. Nie są to wszystkie elementy, które można tu wymienić. W przypadku dynamicznego równoważenia obciążenia jest jeszcze np. komponent odpowiedzialny za negocjacje, który pozwala współpracować różnym komponentom na różnych komputerach poprzez składanie ofert, ich żądanie i przyjmowanie. Innym komponentem jest komponent odpowiedzialny za zbieranie i przechowywanie informacji o stanie systemu (obciążenie procesora, długość kolejek, informacje o procesach itd.).
                  </p>
                  <br>
                  <br>
                  <b style=COLOR:#3d85c6><font size=3>Klasyfikacja metod równoważenia obciążenia</font></b><br>
                  <hr size=2><br>
                </div>
                <div id=mi08 style=TEXT-ALIGN:left>
                  <img src="images/dcjpvv6n_2352z5m862rh_b.png" style=HEIGHT:341px;WIDTH:500px><br>
                  <br>
                  Na rysunku została przedstawiona przykładowa klasyfikacja algorytmów równoważenia obciążenia.
                  <p>
                    <br>
                  </p>
                  <p>
                    Na najwyższym poziomie <b>wyróżniono</b> <b>lokalne</b> (ang. <i>local</i> ) i <b>globalne</b> (ang. <i>global</i> ) równoważenie obciążenia. Ze względu na temat wykładu my zajmiemy się tą drugą klasą algorytmów.<br>
                  </p>
                  <p>
                    <br>
                  </p>
                  <p>
                    Po zejściu na niższy poziom zauważymy dwa kolejne typy algorytmów: <b>statyczne</b> (ang. <i>static</i> ) i <b>dynamiczne</b> (ang. <i>dynamic</i> ). Algorytmy statyczne charakteryzują się przede wszystkim tym, że zadania są tutaj przypisywane do procesorów <i>a</i> <i>priori</i> tzn. przed rozpoczęciem ich wykonywania. Po rozpoczęciu wykonywania, proces nie może już ulec przemieszczeniu.<br>
                  </p>
                  <p>
                    <br>
                  </p>
                  <p>
                    Algorytmy statyczne można podzielić na: algorytmy <b>optymalne</b> (ang. <i>optimal</i> ) oraz <b>suboptymalne</b> (ang. <i>sub-optimal</i> ).
                  </p>
                  <p>
                    W wypadku wyboru gałęzi z dynamicznym równoważeniem obciążenia, dostaniemy dwa odgałęzienia w postaci algorytmów <b>scentralizowanych</b> (ang. <i>centralized</i> ) i <b>rozproszonych</b> (ang. <i>distributed</i> ). W pierwszym przypadku odpowiedzialność za szeregowanie procesów ponosi jedna wybrana maszyna. Z drugiej strony w rozproszonych algorytmach decyzja podejmowana jest przez kilka węzłów obliczeniowych.<br>
                  </p>
                  <p>
                    <br>
                  </p>
                  <p>
                    Wśród rozproszonych dynamicznych algorytmów szeregowania procesów można wyróżnić dwie dodatkowe kategorie: algorytmy, które bazują na współpracy pomiędzy węzłami oraz algorytmy, które tej współpracy nie wykorzystują.<br>
                  </p>
                  <p>
                    <br>
                  </p>
                  <p>
                    Obok przedstawionych kryteriów klasyfikacyjnych algorytmów równoważenia obciążenia, istnieją też inne, nie przedstawione na rysunku:
                  </p>
                  <p>
                    <br>
                  </p>
                  <p>
                    – algorytmy adaptacyjne (ang<i>.</i> <i>adaptive</i> ), czyli takie które potrafią wykorzystać poprzednie stany systemu przy podejmowaniu decyzji, a nie tylko bieżący stan, jak to robią algorytmy nieadaptacyjne;<br>
                  </p>
                  <p>
                    <br>
                  </p>
                  <p>
                    – algorytmy, które stosują strategię zapoczątkowania równoważenia obciążenia przez serwer (ang<i>.</i> <i>server-iitiative</i> ) – serwer szuka zbyt obciążonych maszyn i np. wysyła część zadań na inne mniej zajęte maszyny – lub przez źródło (ang<i>.</i> <i>source-initiative</i> ), które jest zbyt obciążone pracą;<br>
                  </p>
                  <p>
                    <br>
                  </p>
                  <p>
                    – algorytmy, które wykorzystują negocjowanie;<br>
                  </p>
                  <p>
                    <br>
                  </p>
                  <p>
                    – algorytmy bez wywłaszczania (ang. <i>non-pre-emptive</i> ) tzn. takie, które przydzielają tylko nowoutworzone zadania. Algorytmy z wywłaszczaniem mogą z kolei przerywać procesy w trakcie wykonywania i je przenosić.
                  </p>
                  <br>
                  <br>
                </div>
                <b style=COLOR:#3d85c6><font size=3>Statyczne równoważenie obciążenia</font></b><br>
                <hr size=2>
              </div>
              <br>
            </div>
            <div id=k_g4 style=TEXT-ALIGN:left>
              <img src="images/dcjpvv6n_2353g7nzk2d3_b.png" style=HEIGHT:342px;WIDTH:500px><br>
              <br>
              <p>
                <br>
                Statyczny model równoważenia obciążenia, jak zostało wcześniej wspomniane, zakłada że zadania są przypisywane do odpowiednich procesorów przed ich uruchomieniem. Decyzja o uruchomieniu procesów na odpowiednich maszynach podejmowana jest w sposób <b>deterministyczny</b> lub <b>probabilistyczny</b> . W deterministycznym podejściu algorytmy używają informacji o własnościach węzłów obliczeniowych i charakterystyce procesów, które mają być uszeregowane na tych węzłach. Probabilistyczny model szeregowania korzysta tylko ze statycznych informacji o węzłach, czyli z informacji, które się w ogólności nie zmieniają (np.: topologia sieci, moc obliczeniowa węzła).<br>
              </p>
              <p>
                <br>
              </p>
              <p>
                Typowymi kryteriami, których używa się podczas rozwiązywania problemu są m.in.: minimalizowanie czasu ukończenia procesów, minimalizacja zużycia zasobów obliczeniowych, maksymalizacja przepustowości systemu.<br>
              </p>
              <p>
                <br>
              </p>
              <p>
                Podsumowując model deterministyczny i probabilistyczny można powiedzieć, że ten pierwszy jest trudny do optymalizacji, a jego koszt implementacji często przewyższa koszt implementacji drugiego modelu.
              </p>
              <br>
              <br>
              <b style=COLOR:#3d85c6><font size=3>Algorytm A* </font></b><br>
              <hr size=2>
            </div>
            <br>
          </div>
          <div id=hoz1 style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2355c2x47cd5_b.png" style=HEIGHT:344px;WIDTH:500px><br>
            <br>
            Algorytm A* jest algorytmem, który może posłużyć m.in. do statycznego równoważenia obciążenia. Poniżej opiszemy politykę wyboru miejsca, w którym ma być uruchomiony dany proces, gdyż cały algorytm polega na odpowiednim przypisaniu procesów do procesorów.
            <p>
              <br>
            </p>
            <p>
              Zakładamy, że system składa się z <i>n</i> procesorów i <i>m</i> procesów. Dla każdego procesu mamy podany koszt jego uruchomienia na każdym procesorze (macierz kosztów na slajdzie). Algorytm używa struktury drzewa do znalezienia najlepszego rozwiązania. Proces poszukiwania rozwiązania zaczyna się od korzenia drzewa, miejsca w którym jeszcze żaden proces nie jest przypisany do procesora. Każdy poziom w drzewie oznacza przypisanie jednego procesu do określonego procesora. Liście drzewa oznaczają kompletne rozwiązanie, czyli przypisanie wszystkich procesów do procesorów. Podczas schodzenia w głąb drzewa dla każdego węzła <i>n</i> w drzewie obliczany jest koszt <i>C(n</i> <i>).</i> Ta wartość jest oceną najtańszego rozwiązania zawierającego dany węzeł, biorąc pod uwagę koszt komunikacji i uruchomienia. Koszt <i>C(n</i> <i>)</i> tworzy suma dwóch składników: <i>f(n</i> <i>)</i> – koszt bieżącego, częściowego rozwiązania z pierwszymi <i>k</i> zadaniami przypisanymi do procesorów; <i>g(n</i> <i>)</i> – dolne ograniczenie szacowanego kosztu ścieżki w drzewie, poczynając od węzła <i>n</i> do liścia, który reprezentuje pełne rozwiązanie. Za każdym razem algorytm wybiera węzeł z dołu <i>bieżącego</i> drzewa o minimalnym koszcie i rozpatruje przypisanie kolejnego procesu. Algorytm zatrzymuje się gdy dotrze do rozwiązania. Do obliczenia <i>f(n</i> <i>)</i> jest brany procesor z największym obciążeniem komunikacyjnym (koszt komunikacji podany jest na grafie procesów) i obliczeniowym. Wartość <i>g(n</i> <i>)</i> jest kosztem komunikacji pomiędzy najbardziej obciążonym węzłem, a węzłami, którym nie przypisano do tej pory zadań. Dla uproszczenia wszystkie procesy reprezentowane są jako graf nieskierowany, gdzie każdy węzeł oznacza proces, a krawędź wymagania komunikacyjne. Poza tym zakłada się, że każdy procesor może komunikować się ze wszystkimi innymi procesorami w systemie i nie muszą one być połączone koniecznie bezpośrednio ze sobą.
            </p>
            <br>
            <br>
            <div id=mg5c style=TEXT-ALIGN:left>
              <img src="images/dcjpvv6n_2356fdzrwndc_b.png" style=HEIGHT:341px;WIDTH:500px><br>
              <br>
              Prześledzimy teraz działanie algorytmu A* dla sieci procesów i procesorów zaprezentowanych na poprzednim slajdzie. Macierz kosztów <i>M</i> również bierzemy z poprzedniego slajdu.<br>
              <br>
              <p>
                Dla uproszczenia prezentacji przykładu, zakładamy następującą notację przypisania procesów do procesorów: procesy uporządkowane są w ciąg według swoich identyfikatorów (<i>t0</i> <i>,</i> <i>t1</i> <i>,</i> <i>t2</i> , …, <i>tn</i> ), a każdemu procesowi z ciągu, który ma być wykonany na pewnym procesorze, odpowiada identyfikator tego procesora. W ten sposób uzyskujemy ciąg identyfikatorów (na slajdzie numerów) procesorów przypisanych do kolejnych procesów. Dodatkowo jeżeli proces nie ma przypisanego żadnego procesora oznaczamy to w ciągu literą „X”.<br>
              </p>
              <p>
                <br>
              </p>
              <p>
                Dany mamy ciąg (2 0 2 X X) przypisania procesów do procesorów (proces <i>t0</i> przypisany do procesora <i>p2</i> , <i>t1</i> do <i>p0</i> , <i>t2</i> do <i>p2</i> ). Chcemy teraz obliczyć koszt takiego przypisania <i>C(2</i> 0 2 X X). Musimy więc obliczyć dwie wartości: koszt <i>f(2</i> 0 2 X X) oraz koszt <i>g(2</i> 0 2 X X). Na slajdzie podano koszt wykonania poszczególnych procesów na odpowiednich procesorach (np. <i>M(t1</i> <i>,</i> <i>p0</i> <i>)</i> <i>=</i> <i>14</i> ). Obciążenie procesora (oznaczone jako funkcja <i>Ob(identyfikator_procesora</i> <i>))</i> obliczane jest poprzez zsumowanie kosztów wykonania przypisanych mu procesów i kosztów komunikacji z innymi przypisanymi już procesami. Po obliczeniu obciążenia procesorów <i>p0</i> oraz <i>p2</i> widzimy, że procesor <i>p2</i> jest bardziej obciążony, dlatego to <i>p2</i> jest brane pod uwagę przy obliczaniu kosztu <i>f</i> . <i>f(2</i> 0 2 X X) liczymy sumując koszty wykonania procesów na tym procesorze (<i>M(t0</i> <i>,</i> <i>p2</i> <i>)</i> <i>+</i> <i>M(t2</i> <i>,</i> <i>p2</i> <i>))</i> oraz maksymalny koszt komunikacyjny tego procesora (dla procesora <i>p2</i> i ciągu przypisań (2 0 2 X X) będzie to 8). Koszt <i>g(2</i> 0 2 X X) liczymy z kolei sumując koszty komunikacji pomiędzy procesami na najbardziej obciążonym procesorze <i>p2</i> (są to procesy <i>t0</i> i <i>t2</i> <i>),</i> z nieprzypisanymi dotąd procesami czyli <i>t3</i> i <i>t4</i> . Po zsumowaniu kosztów <i>f(2</i> 0 2 X X) = 23 oraz <i>g(2</i> 0 2 X X) = 16 uzyskujemy całkowity koszt przypisania <i>C(2</i> 0 2 X X) = 39.
              </p>
              <br>
              <br>
              <b style=COLOR:#3d85c6><font size=3>Dynamiczne równoważenie obciążenia</font></b><br>
              <hr size=2>
            </div>
            <br>
          </div>
          <div id=w8vp style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2357hpqwp5gk_b.png" style=HEIGHT:344px;WIDTH:500px><br>
            <br>
            Algorytmy dynamicznego równoważenia obciążenia, w przeciwieństwie do algorytmów statycznych, starają się równoważyć obciążenie dynamicznie podczas gdy procesy są już być może uruchomione. Nadrzędnym celem algorytmów dynamicznego równoważenia obciążenia jest znalezienie najlepszego z pewnego punktu widzenia umiejscowienia w systemie wszystkich procesów. Decyzje podejmowane są na podstawie bieżącego stanu systemu rozproszonego, co jest jedną z podstawowych trudności w tym wypadku.
            <p>
              <br>
            </p>
            <p>
              Informacje o stanie systemu mogą być przechowywane w sposób scentralizowany lub rozproszony. Dodatkową cechą algorytmów dynamicznego równoważenia obciążenia są relacje między komponentami decyzyjnymi w różnych węzłach systemu. Mogą one ze sobą współpracować w celu podjęcia wspólnej decyzji lub komponenty mogą same podejmować decyzje. W drugim przypadku decyzje wpływają tylko na lokalną wydajność i mogą być sprzeczne z decyzjami innych, generując konflikty zasobowe.
            </p>
            <br>
            <br>
            <b style=COLOR:#3d85c6><font size=3>Algorytm Bryanta i Finkela</font></b><br>
            <hr size=2><br>
          </div>
          <div id=c:8. style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2358c58h9kf3_b.png" style=HEIGHT:342px;WIDTH:500px><br>
            <br>
            Jest to dynamiczny algorytm, działający w środowisku fizycznie rozproszonym. Przebiega następująco. Komputer <i>K1</i> wysyła zapytanie do jednego ze swoich najbliższych sąsiadów, komputera <i>K2</i> . Zapytanie to ma na celu dwie rzeczy: informuje komputer <i>K2</i> , o tym że <i>K1</i> chciałby utworzyć parę, która stanowiłaby stabilne środowisko odpowiednie do wędrówki procesów; poza tym zapytanie zawiera listę procesów oraz czasy jakie zajęło ich wykonywanie na <i>K1</i> (ta informacja jest użyta w późniejszym etapie do oszacowania czasu potrzebnego na dokończenie wykonania procesu). <i>K2</i> po otrzymaniu zapytania może wykonać następujące czynności:<br>
            <br>
            <p>
              a) odrzucić zapytanie – w tym momencie <i>K1</i> zmuszone jest do wysłania zapytanie do innego sąsiada;<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              b) utworzyć parę z <i>K1</i> – <i>K1</i> i <i>K2</i> odrzucają wtedy wszystkie nadchodzące do nich zapytania dopóki nie zakończą współpracy ze sobą;<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              c) odłożyć zapytanie <i>K1</i> do czasu gdy <i>K2</i> znajdzie się w stanie umożliwiającym wędrówkę, ponieważ <i>K2</i> może aktualnie przeprowadzać wędrówkę innego procesu – <i>K1</i> musi poczekać do czasu, gdy <i>K2</i> utworzy z nim parę lub go odrzuci (w tym czasie <i>K1</i> nie może wypytywać innych komputerów).<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              Po utworzeniu pary, komputer z większym obciążeniem (np. <i>K1</i> ) wybiera proces do wędrówki na drugi komputer. Jako kryterium dla tej operacji używa się wskaźnika poprawy czasu reakcji <i>k(i</i> <i>)</i> (ang. <i>response</i> <i>time</i> ), który równa się czasowi reakcji <i>T1(i</i> <i>)</i> procesu na maszynie źródłowej podzielonemu przez sumę czasu reakcji <i>T2(i</i> <i>)</i> tego procesu na maszynie docelowej i czasu <i>T12(i</i> <i>)</i> jego przeniesienia na tę maszynę (np. z <i>K1</i> na <i>K2</i> ). <i>T1(i</i> <i>)</i> może być obliczone poprzez oszacowanie czasu <i>TE(i</i> <i>)</i> potrzebnego na ukończenie procesu; czas potrzebny na ukończenie procesu jest równy czasowi <i>T</i> zużytemu do tej pory. Algorytm obliczania <i>T1(i</i> <i>)</i> przedstawiono szczegółowo na ilustracji.<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              W wypadku gdy <i>k(i</i> <i>)&lt;</i> 1 dla wszystkich procesów na <i>K1</i> , <i>K1</i> informuje <i>K2</i> o tym fakcie i para jest zrywana. W przeciwnym razie proces, który rokuje najlepsze nadzieje na poprawienie efektywności wykonywania, jest wybierany do wędrówki. Cała ta procedura wykonywana jest do czasu, gdy nie można poprawić wydajności żadnego procesu na <i>K2</i> .
            </p>
            <br>
            <br>
            <b style=COLOR:#3d85c6><font size=3>Algorytm Baraka i Shiloha</font></b><br>
            <hr size=2><br>
            <div id=t2y8 style=TEXT-ALIGN:left>
              <img src="images/dcjpvv6n_2359frqq57fg_b.png" style=HEIGHT:340px;WIDTH:500px><br>
              <br>
              Algorytm Baraka i Shiloha jest algorytmem do globalnego równoważenia obciążenia. W algorytmie tym zakłada się, że każdy komputer przechowuje informację o obciążeniu pewnej stałej liczby innych komputerów. Co pewien czas informacje o obciążeniach wymieniane są losowo pomiędzy parami komputerów. Przy użyciu tych informacji, algorytm stara się zminimalizować rozbieżności w obciążeniu poszczególnych komputerów.<br>
              <br>
              <p>
                W skład algorytmu wchodzą trzy komponenty składowe.<br>
              </p>
              <p>
                <br>
              </p>
              <p>
                1) Algorytm do obliczania obciążenia procesora, który służy do szacowania lokalnego obciążenia komputera. Lokalne obciążenie obliczane jest co pewien określony czas, a następnie jest uśredniane w danym okresie czasu. W algorytm tym wykorzystywany jest również tzw. wektor obciążenia, <i>L</i> , w którym przechowywane są lokalnie informacje o obciążeniach komputerów. Na pierwszej pozycji wektora <i>L</i> przechowywana jest informacja o lokalnym obciążeniu komputera. Kolejne pozycje wektora <i>L</i> zawierają wartości obciążenia innych komputerów. Wartość <i>L[j</i> <i>]</i> oznacza pozycję <i>j</i> w wektorze obciążenia i zawiera szacowane obciążenie komputera <i>j</i>.<br>
              </p>
              <p>
                <br>
              </p>
              <p>
                2) Kolejnym komponentem jest algorytm wymiany informacji między komputerami, który jest odpowiedzialny za przekazywanie informacji o obciążeniach między komputerami. Wymiana informacji polega w skrócie na przesłaniu pewnej części wektora obciążenia <i>L</i> do innych komputerów, tak aby były dobrze poinformowane o stanie obciążenia.<br>
              </p>
              <p>
                <br>
              </p>
              <p>
                Poniżej opiszemy bardziej szczegółowo działanie algorytmu wymiany informacji.<br>
              </p>
              <p>
                <br>
              </p>
              <p>
                Co pewien czas każdy komputer wykonuje kilka operacji. Aktualizuje informację o wartości swojego obciążenia w wektorze <i>L</i> , a następnie wybiera losowy komputer <i>i</i> i wysyła do niego pierwszą połowę swojego wektora obciążenia, <i>Lr</i> . Po otrzymaniu części wektora obciążenia, każdy komputer oszacowuje obciążenie każdego innego komputera poprzez połączenie otrzymanego wektora ze swoim własnym wektorem obciążenia <i>L</i> . Należy nadmienić, że porządek wartości w wektorze <i>L</i> implikuje wiek informacji. Łączenie połowy wektora obciążenia podczas jego podziału jest pewną formą starzenia danych (ang. <i>aging</i> ). W kolejnym kroku algorytm stara się oszacować obciążenie komputera używając w tym celu średniej liczby procesów, które żądają usługi w pewnej jednostce czasu. Wartość tego obciążenia jest użyta następnie do określenia czasu reakcji (ang. <i>response</i> <i>time</i> ) procesora. Do komputera, który ma najmniejszy czas reakcji można teraz przenieść proces. Specjalny proces działa dodatkowo na każdym komputerze i sprawdza czy są procesy, które mogą być poddane wędrówce.<br>
              </p>
              <p>
                <br>
              </p>
              <p>
                3) Ostatnim komponentem w podejściu Baraka i Shiloha jest migracja procesów, której nie będziemy jednak tutaj już przedstawiać.<br>
              </p>
              <p>
                <br>
              </p>
              <p>
                Algorytm Baraka i Shiloha jest algorytmem optymalnym globalnie przy założeniu, że wektor <i>L</i> ma rozmiar, który jest równy liczbie wszystkich komputerów w sieci.
              </p>
              <br>
              <br>
              <b style=COLOR:#3d85c6><font size=3>Algorytm Baraka i Shiloha - przykład</font></b><br>
              <hr size=2><br>
            </div>
            <div id=o956 style=TEXT-ALIGN:left>
              <img src="images/dcjpvv6n_2360c7x6pcc2_b.png" style=HEIGHT:344px;WIDTH:500px><br>
              <br>
              W przykładzie zaprezentowanym na ilustracji przedstawiono schemat wymiany informacji w algorytmie Baraka i Shiloha. Zakładamy istnienie sieci 4 komputerów: <i>A</i> , <i>B</i> , <i>C</i> oraz <i>D</i> . Każdy z nich przechowuje wektor obciążenia o rozmiarze 4. Wartość wektora należy odczytywać z tabel pionowo, kolejne wiersze odpowiadają kolejnym pozycjom wektora. Każdy komputer posiada kilka wartości swojego wektora obciążenia dla różnych momentów w czasie, co widoczne jest w postaci kolumn w tabeli. Np. trzecia kolumna w tabeli na komputerze <i>A</i> ([8, 3, 6, 4]) oznacza wektor obciążenia uzyskany w wyniku wymiany informacji z innym komputerem. Strzałka skierowana od wektora na jednym komputerze do wektora na drugim komputerze oznacza, że ten pierwszy wybrał drugiego w celu wymiany informacji.<br>
              <br>
              <p>
                Prześledźmy teraz przykład wymiany informacji o obciążeniu. Wartości oznaczone jako <i>X</i> na rysunku są wartościami obciążenia, które nie są dla nas istotne i oznaczają dowolną liczbę. Posłużymy się w tym celu komputerem <i>A</i> . Obciążenie komputera <i>A</i> wynosi 12. W pewnym momencie działania algorytmu równoważenia obciążenia komputera <i>A</i> wybrał losowo komputer <i>B</i> w celu wymiany z nim informacji. Wektor <i>Lr</i> , który zostanie przekazany z komputera <i>B</i> do <i>A</i> ma postać [6 X]. Po połączeniu lokalnego wektora z otrzymanym od <i>B</i> wektorem <i>Lr</i> <i>,</i> na komputerze <i>A</i> uzyskujemy nowy wektor [10 6 X X]. W kolejnym kroku komputer <i>A</i> wybiera do wymiany komputer <i>D</i> . W międzyczasie aktualizowana jest również informacja o wartość lokalnego obciążenia, która teraz dla <i>A</i> wynosi 8. Z komputera <i>D</i> , <i>komputer</i> <i>A</i> otrzymuje wektor <i>Lr</i> równy [3, 4]. Ostatecznie wektor obciążenia <i>L</i> na <i>A</i> wynosi [8, 3, 6, 4].
              </p>
            </div>
          </div>
        </div>
      </div>
    </div>
  </div>
</div>
<br></body>
</html>